#pragma once

#include <iostream>

namespace solution_025
{

struct ListNode
{
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution
{
public:
    ListNode* reverseKGroup(ListNode* head, int k)
    {
        if (k == 1)
            return head;
        ListNode root(0, head);
        auto prev = &root;
        while (prev)
            prev = swap_k(prev, k);
        return root.next;
    }

private:
    ListNode* swap_k(ListNode* prev, int k)
    {
        auto next_node = prev->next;
        while (k && next_node) {
            next_node = next_node->next;
            --k;
        }
        if (k > 0)
            return nullptr;

        auto prev_backup = prev;
        for (auto node = prev->next; node != next_node; ) {
            auto next = node->next;
            node->next = prev;
            prev = node;
            node = next;
        }
        prev_backup->next->next = next_node;
        std::swap(prev_backup->next, prev);
        return prev;
    }
};

}  /* namespace solution_025 */
